package org.kfive.nova.algorithm;

import com.google.common.base.Preconditions;
import com.google.common.base.Strings;
import com.google.common.collect.Lists;
import com.google.common.primitives.Chars;

import java.util.List;

/*
* Kmp.java
* Created  by  lizhanwu
* Created on 2016-5-25 11:27
*/
public class Kmp {

    private List<Integer> jumpTable(String pattern){
        Preconditions.checkArgument(!Strings.isNullOrEmpty(pattern),"匹配模式字符串不能为空");
        List<Integer> table = Lists.newArrayList();
        table.add(0,0);
        for (int i=1,k=0;i<pattern.length();i++){
            while (k>0&& Chars.compare(pattern.charAt(i),pattern.charAt(k))!=0){
                k = table.get(k-1);
            }
            if(Chars.compare(pattern.charAt(i),pattern.charAt(k))==0){
                k++;
            }
            table.add(i,k);
        }
        return table;
    }

    public List<String> kmp(String source,String pattern){
        Preconditions.checkArgument(!Strings.isNullOrEmpty(source),"待匹配字符串不能为空");
        Preconditions.checkArgument(!Strings.isNullOrEmpty(pattern),"匹配模式字符串不能为空");
        List<String> result = Lists.newArrayList();
        List<Integer> next = jumpTable(pattern);
        for (int i=0,j=0;i<source.length();i++){
            while (j>0&Chars.compare(source.charAt(i),pattern.charAt(j))!=0){
                j = next.get(j-1);
            }
            if(Chars.compare(source.charAt(i),pattern.charAt(j))==0){
                j++;
            }
            if(j==pattern.length()){
                result.add(source.substring(i-j+1,i+1));
                j=0;
            }
        }
        return result;
    }
    
}
